/*
 * =====================================================================================
 *
 *       Filename:  graph.h
 *
 * =====================================================================================
 */

/*
 * Structures definitions
 */
#include <stdint.h>

#include "list.h"

#ifndef __GRAPH_HEADER

#define __GRAPH_HEADER

#if 0
Breadth-First Search (BFS)
Depth-First Search  (DFS)
Single Source Shortest Path (SSSP)
All-Pair Shortest Path (APSP)
Minimum Spanning Tree (MST)
Graph Matching
Graph Partition

#endif

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1
#define INFI -10

typedef struct GRAPH_VERTEX {
	uint32_t id;
	double cost;
	uint32_t parent;   /* integer index of parent vertex  */

	int color;
	int dist;	  /* distance from source/root vertex of tree (only in BFS) */
	int d;		  /* vertex discovery time (only in DFS) */
	int f;		  /* vertex finishing time (only in DFS) */

	int indegree;
	int outdegree;
	void *value;
} Graph_node;

typedef struct link {
	uint32_t source, dest;
	double cost;
	void *value;
} Graph_link;

typedef enum GRAPH_TYPES {
	simple = 0,
	hash_vertex,
	hash_source,
	hash_dest
} Graph_type;

typedef list Graph_vertex;
typedef list Graph_edge;

typedef struct GRAPHS {

	uint32_t graph_type;
	uint32_t hash_base;
	uint32_t v_slots, e_slots;

	Graph_vertex *vertex;
	Graph_edge *edge;

	Graph_vertex **hash_v;
	Graph_edge **hash_e;

	void (*vh_func) (void *ptr);
	void (*eh_func) (void *ptr);
	void (*free) (void *ptr);
	int (*match) (const void*ptr, const void*key);

} Graphs;

Graphs *graph_create(uint32_t,uint32_t,uint32_t);
void graph_set_vh_func(Graphs *graph,void (*hashfunc)(void *));
void graph_set_eh_func(Graphs *graph,void (*hashfunc)(void *));
void graph_release(Graphs *);

Graph_node *graph_node_create() ;
void graph_node_release(Graph_node *,void (*vfree)(void *),void (*nfree)(void *)) ;

void graph_add_node(Graphs *graph, Graph_node *,
	        int(*ncmp)(const void *,const void *));

void graph_del_node(Graphs *graph, Graph_node *,
	       int(*ncmp)(const void *,const void *));

void graph_bDel_node(Graphs *graph, Graph_vertex *,
	       int(*ncmp)(const void *,const void *));

void graph_add_edge(Graphs *graph, Graph_link *);

void graph_del_edge(Graphs *graph, Graph_link *,
	       int(*ncmp)(const void *,const void *));

void graph_bDel_edge(Graphs *graph, Graph_edge *,
	       int(*ncmp)(const void *,const void *));

Graph_node *graph_get_node(Graphs *graph, Graph_link *,
	       int(*ncmp)(const void *,const void *));

unsigned int graph_get_NodeCount(Graphs *graph);

Graph_link *graph_get_edge(Graphs * graph, unsigned int u, unsigned int v);
unsigned int graph_get_EdgeCount(Graphs *graph);

int graph_IsEdge(Graphs *graph, unsigned int u, unsigned int v);
int graph_IsEmpty(Graphs *graph);

unsigned int graph_degree(Graphs *graph, unsigned int n);

void graph_add_gNode_sorted(Graphs *graph, Graph_node *Node, int (*cmp) (const void *a, const void *b));
void graph_remove_Node(Graphs *graph, Graph_node *Node);

void gNode_add_edge(Graphs *, Graph_link *);
void gNode_add_edge_sorted(Graphs *, Graph_link *);
void gNode_remove_edge(Graphs *, Graph_link *);

void gNode_add_edge_to_Node(Graph_node *from, Graph_node *to, double weight);
void gNode_add_edge_to_Node_sorted(Graph_node *from, Graph_node *to, double weight);
void gNode_remove_edge_to_Node(Graph_node *from, Graph_node *to);
void gNode_remove_edge_from_Node(Graph_node *from, Graph_node *to);

void graph_sort_vertices(Graphs *graph, int (*cmp) (const void *a, const void *b));
void gNode_sort_edges(Graph_node *Node);

unsigned int graph_get_ConnectedComponentCount(Graphs *graph);

unsigned int graph_inner_degree(Graphs *graph, unsigned int n);
unsigned int graph_outer_degree(Graphs *graph, unsigned int n);

void GraphPrintNodes(Graphs *graph);
void GraphPrintEdges(Graphs *graph);
void GraphPrint(Graphs *graph);
void GraphPrintConnectedComponent(Graphs *graph);

#endif
